package 中等.二分查找;

/**
 * 给你一个整数数组 ranks ，表示一些机械工的 能力值 。ranksi 是第 i 位
 * 机械工的能力值。能力值为 r 的机械工可以在 r * n2 分钟内修好 n 辆车。
 * 同时给你一个整数 cars ，表示总共需要修理的汽车数目。
 * 请你返回修理所有汽车 最少 需要多少时间。
 * 注意：所有机械工可以同时修理汽车。
 */
public class 修车的最少时间_2594 {

    public static void main(String[] args) {

        修车的最少时间_2594 impl = new 修车的最少时间_2594();

        System.out.println(impl.repairCars(new int[]{31, 31, 5, 19, 19, 10, 31, 18, 19, 3, 16, 20, 4, 16, 2, 25, 10, 16, 23, 18, 21, 23, 28, 6, 7, 29, 11, 11, 19, 20, 24, 19, 26, 12, 29, 29, 1, 14, 17, 26, 24, 7, 11, 28, 22, 14, 31, 12, 3, 19, 16, 26, 11}, 736185));

    }

    /**
     * 二分查找
     * 时间越多可以修的车总数越多，有单调性，可以用二分查找枚举最少需要
     * 多少时间，已知有 x 分钟，r * n^2 = x 那么可以修 根号下 x/r 辆车
     * 注意：右边界可以是全部由第一个人修需要的时间
     */
    public long repairCars(int[] ranks, int cars) {
        long ans = Long.MAX_VALUE;
        // 注意需要转成 long 类型
        long left = 0, right = 1L * ranks[0] * cars * cars;
        while (left <= right) {
            long mid = left + (right - left) / 2;
            if (canRepair(ranks, cars, mid)) {
                ans = Math.min(ans, mid);
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

    private boolean canRepair(int[] ranks, int cars, long minute) {
        int curCars = 0;

        for (int rank : ranks) {
            // 已知有 x 分钟，r * n^2 = x 那么可以修 根号下 x/r 辆车
            curCars += Math.sqrt(minute / rank);
        }

        return curCars >= cars;
    }

}
